package hash;


public class KVHashBucket <K,V>{
    // 存放链表数组
   Node<K,V>[]array;

    // 实际元素个数
    int useSize;


    private static final int DEFAULTSIZE=10;


    // 定义一个内部类为节点
    static class Node<K,V> {
        V val;
        Node<K,V> next;

        K key;
        public Node(K key,V val) {
            this.key=key;
            this.val = val;
        }
    }



    public KVHashBucket() {
        array= (Node<K, V>[]) new Node[DEFAULTSIZE];

    }

    /**
     * 插入方法
     * @param val 需要插入的数据
     */
    void put(K key,V val) {

        // 判断是否满
        if (isFull()) {
            insertFunc2(key,val);
            return;
        }

        insertFunc1(key,val);

    }

    /**
     * 未满时普通插入
     * @param val 需要插入的数据
     */

    private void insertFunc1(K key,V val) {
        int sz=array.length;
        int k=key.hashCode();
        int index= k % sz;

        // 如果出现 key 重复 就修改 val 值
        Node<K,V> cur=array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val=val;
                return;
            }
            cur=cur.next;
        }

        Node<K,V> node=new Node<K,V>(key,val);

        node.next=array[index];
        array[index]=node;
        useSize++;
    }

    /**
     * 扩容方法
     * @param val 插入数据
     * 先扩容一个新数组
     * 然后把旧数组整合放入新数组
     * 最后旧数组成为新数组
     */

    private void insertFunc2(K key ,V val) {
       Node<K,V> cur=null;

       Node<K,V>[] newArray= (Node<K, V>[]) new Node[2 * array.length];

        int newLength = 2 * array.length;

        for (int i = 0; i < array.length; i++) {

            cur=array[i];
            while (cur != null) {
                K m = cur.key;

                // 先让 node 记住 cur 的下个节点
                Node<K,V> node = cur.next;
                int k=m.hashCode();
                int index= k % newLength;

                cur.next = newArray[index];
                newArray[index] = cur;

                cur=node;
            }

        }

       Node<K,V> til=new Node<K,V>(key,val);
        int k=key.hashCode();
        int index=k%newLength;

        // 如果出现 key 重复 就修改 val 值
        Node<K,V> curN=array[index];
        while (curN != null) {
            if (curN.key == key) {
                curN.val=val;
                return;
            }
            curN=curN.next;
        }


        til.next=newArray[index];

        newArray[index]=til;

        useSize++;

        array=newArray;
    }

    /**
     * 查找该节点
     * @param key 需要查找的数据
     * @return 返回该数据的节点
     */
    public V get(K key) {
        if (isEmpty()) return null;

        int k=key.hashCode();
        int index = k % array.length;
        Node<K,V> cur=array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.val;
            }
            cur=cur.next;
        }

        return null;
    }

    /**
     * 查找是否该节点
     * @param key 需要查找的数据
     * @return 返回是否找到
     */

    public   boolean contains(K key) {
        if (isEmpty()) return false;

        int k=key.hashCode();
        int index=k % array.length;



        Node<K,V> cur=array[index];

        while (cur != null) {
            if (cur.val.equals(key)) {
                return true;
            }
            cur=cur.next;
        }



        return false;
    }



    public boolean remove(K key) {
        if (isEmpty()) return false;

        int k=key.hashCode();
        int index = k % array.length;

        Node<K,V> cur = array[index];

        Node<K,V> node = cur;

        if (cur.key==key) {

            array[index]=cur.next;
            return true;
        }
        while (cur != null) {
            if (cur.key.equals(key)) {
                node.next = cur.next;
                useSize--;
                return true;
            }
            node = cur;
            cur = cur.next;
        }

        return false;
    }

    /**
     * 判断是否满
     * @return 返回结果
     */
    private boolean isFull() {
        return (useSize*1.0/array.length) >= 0.75;
    }

    /**
     * 判断是否为空
     * @return 返回结果
     */


    private boolean isEmpty() {
        return useSize==0;
    }
}
